      SUBROUTINE F01BRU(N,ICN,LICN,IP,LENR,ARP,IB,NUM,LOWL,NUMB,PREV)
C     MARK 7 RELEASE. NAG COPYRIGHT 1978
C     MARK 11.5(F77) REVISED. (SEPT 1985.)
C     DERIVED FROM HARWELL LIBRARY ROUTINE MC13E
C
C     FINDS A SYMMETRIC PERMUTATION WHICH PERMUTES A SPARSE MATRIX
C     TO BLOCK LOWER TRIANGULAR FORM, GIVEN THE COLUMN NUMBERS OF
C     THE NON-ZEROS IN EACH ROW OF THE MATRIX.
C
C     ARP(I) IS ONE LESS THAN THE NUMBER OF UNSEARCHED EDGES
C     .     LEAVING NODE I.  AT THE END OF THE ALGORITHM IT IS SET
C     .     TO A PERMUTATION WHICH PUTS THE MATRIX IN BLOCK LOWER
C     .     TRIANGULAR FORM.
C     IB(I) IS THE POSITION IN THE ORDERING OF THE START OF THE ITH
C     .     BLOCK.  IB(N+1-I) HOLDS THE NODE NUMBER OF THE ITH NODE
C     .     ON THE STACK.
C     LOWL(I) IS THE SMALLEST STACK POSITION OF ANY NODE TO WHICH A
C     .     PATH FROM  HAS BEEN FOUND.  IT IS SET TO N+1 WHEN NODE I
C     .     IS REMOVED FROM THE STACK.
C     NUMB(I) IS THE POSITION OF NODE I IN THE STACK IF IT IS ON
C     .     IT, IS THE PERMUTED ORDER OF NODE I FOR THOSE NODES
C     .     WHOSE FINAL POSITION HAS BEEN FOUND AND IS OTHERWISE
C     .     ZERO.
C     PREV(I) IS THE NODE AT THE END OF THE PATH WHEN NODE I WAS
C     .     PLACED ON THE STACK.
C
C
C     ICNT IS THE NUMBER OF NODES WHOSE POSITIONS IN FINAL ORDERING
C     HAVE BEEN FOUND.
C     .. Scalar Arguments ..
      INTEGER           LICN, N, NUM
C     .. Array Arguments ..
      INTEGER           ARP(N), IB(N), ICN(LICN), IP(N), LENR(N),
     *                  LOWL(N), NUMB(N), PREV(N)
C     .. Local Scalars ..
      INTEGER           DUMMY, I, I1, I2, ICNT, II, ISN, IST, IST1, IV,
     *                  IW, J, K, LCNT, NNM1, STP
C     .. Intrinsic Functions ..
      INTRINSIC         MIN
C     .. Executable Statements ..
      ICNT = 0
C     NUM IS THE NUMBER OF BLOCKS THAT HAVE BEEN FOUND.
      NUM = 0
      NNM1 = N + N - 1
C
C     INITIALIZATION OF ARRAYS.
      DO 20 J = 1, N
         NUMB(J) = 0
         ARP(J) = LENR(J) - 1
   20 CONTINUE
C
      DO 180 ISN = 1, N
C        LOOK FOR A STARTING NODE
         IF (NUMB(ISN).NE.0) GO TO 180
         IV = ISN
C        IST IS THE NUMBER OF NODES ON THE STACK ... IT IS THE STACK
C        POINTER.
         IST = 1
C        PUT NODE IV AT BEGINNING OF STACK.
         LOWL(IV) = 1
         NUMB(IV) = 1
         IB(N) = IV
C
C        THE BODY OF THIS LOOP PUTS A NEW NODE ON THE STACK OR
C        BACKTRACKS.
         DO 160 DUMMY = 1, NNM1
            I1 = ARP(IV)
C           HAVE ALL EDGES LEAVING NODE IV BEEN SEARCHED.
            IF (I1.LT.0) GO TO 60
            I2 = IP(IV) + LENR(IV) - 1
            I1 = I2 - I1
C
C           LOOK AT EDGES LEAVING NODE IV UNTIL ONE ENTERS A NEW NODE OR
C           ALL EDGES ARE EXHAUSTED.
            DO 40 II = I1, I2
               IW = ICN(II)
C              HAS NODE IW BEEN ON STACK ALREADY.
               IF (NUMB(IW).EQ.0) GO TO 140
C              UPDATE VALUE OF LOWL(IV) IF NECESSARY.
               LOWL(IV) = MIN(LOWL(IV),LOWL(IW))
   40       CONTINUE
C
C           THERE ARE NO MORE EDGES LEAVING NODE IV.
            ARP(IV) = -1
C           IS NODE IV THE ROOT OF A BLOCK.
   60       IF (LOWL(IV).LT.NUMB(IV)) GO TO 120
C
C           ORDER NODES IN A BLOCK.
            NUM = NUM + 1
            IST1 = N + 1 - IST
            LCNT = ICNT + 1
C           PEEL BLOCK OFF THE TOP OF THE STACK STARTING AT THE TOP AND
C           WORKING DOWN TO THE ROOT OF THE BLOCK.
            DO 80 STP = IST1, N
               IW = IB(STP)
               LOWL(IW) = N + 1
               ICNT = ICNT + 1
               NUMB(IW) = ICNT
               IF (IW.EQ.IV) GO TO 100
   80       CONTINUE
  100       IST = N - STP
            IB(NUM) = LCNT
C           ARE THERE ANY NODES LEFT ON THE STACK.
            IF (IST.NE.0) GO TO 120
C           HAVE ALL THE NODES BEEN ORDERED.
            IF (ICNT.LT.N) GO TO 180
            GO TO 200
C
C           BACKTRACK TO PREVIOUS NODE ON PATH.
  120       IW = IV
            IV = PREV(IV)
C           UPDATE VALUE OF LOWL(IV) IF NECESSARY.
            LOWL(IV) = MIN(LOWL(IV),LOWL(IW))
            GO TO 160
C
C           PUT NEW NODE ON THE STACK.
  140       ARP(IV) = I2 - II - 1
            PREV(IW) = IV
            IV = IW
            IST = IST + 1
            LOWL(IV) = IST
            NUMB(IV) = IST
            K = N + 1 - IST
            IB(K) = IV
  160    CONTINUE
  180 CONTINUE
C
C     PUT PERMUTATION IN THE REQUIRED FORM.
  200 DO 220 I = 1, N
         II = NUMB(I)
         ARP(II) = I
  220 CONTINUE
      RETURN
      END
